package leetcode_1201_1300;

import java.util.PriorityQueue;

public class LeeCode_1240 {
    public static void main(String[] args) {
//        System.out.println(tilingRectangle(5, 8));
//        System.out.println(tilingRectangle(11, 3));
//        System.out.println(tilingRectangle(13, 12));
        System.out.println(tilingRectangle(20, 17));
    }
    private static int tilingRectangle(int n, int m) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0])
                return o1[1] - o2[1];
            return o1[0] - o2[0];
        });
        boolean[][] grid = new boolean[n][m];
        int[][][] tab = new int[n][m][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tab[i][j] = new int[]{i, j};
                queue.add(tab[i][j]);
            }
        }
        int[] ans = new int[1];
        ans[0] = Integer.MAX_VALUE;
        dfs(tab, queue, 0, grid, ans);
        return ans[0];
    }
    private static void dfs(int[][][] tab, PriorityQueue<int[]> queue, int sum, boolean[][] grid, int[] ans){
        if (sum >= ans[0]){
            return;
        }
        if (queue.size() == 0){
            ans[0] = sum;
            return;
        }
        int n = grid.length, m = grid[0].length;
        int[] p = queue.poll();
        int x = p[0], y = p[1];
        int max = 0;
        int[] pd = new int[]{x, y}, pu = new int[]{x, y};
        while (x + max < n && y + max < m){
            pd[0] = x + max;
            pd[1] = y;
            pu[0] = x;
            pu[1] = y + max;
            boolean flag = true;
            while (pd[0] != pu[0]){
                if (grid[pd[0]][pd[1]] || grid[pu[0]][pu[1]]){
                    flag = false;
                    break;
                }
                pd[1]++;
                pu[0]++;
            }
            if (!flag)
                break;
            max++;
        }
        for (int i = x; i < x + max; i++) {
            for (int j = y; j < y + max; j++) {
                grid[i][j] = true;
                queue.remove(tab[i][j]);
            }
        }
        for(int d = max; d >= 0; d--){
            dfs(tab, queue, sum + 1, grid, ans);
            //状态恢复
            for(int i = x + d - 1; i >= x; i--){
                grid[i][y + d - 1] = false;
                queue.add(tab[i][y + d - 1]);
            }
            for(int j = y + d - 1; j >= y; j--){
                if (j == y + d - 1)
                    continue;
                grid[x + d - 1][j] = false;
                queue.add(tab[x + d - 1][j]);
            }
        }
    }
}